home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / get_index.c.z / get_index.c
C/C++ Source or Header  |  1997-09-09  |  47KB  |  1,374 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2. #include "glimpse.h"
  3. #include "defs.h"
  4.  
  5. #if    BG_DEBUG
  6. extern    FILE    *debug;
  7. #endif    /*BG_DEBUG*/
  8. extern    char    INDEX_DIR[MAX_LINE_LEN];
  9. extern    int    Only_first;
  10. extern    int    PRINTAPPXFILEMATCH;
  11. extern    int    OneFilePerBlock;
  12. extern    int    StructuredIndex;
  13. extern    int    WHOLEFILESCOPE;
  14. extern    unsigned int *dest_index_set;
  15. extern    unsigned char *dest_index_buf;
  16. extern    int    mask_int[32];
  17. extern    int    errno;
  18. extern    int    ByteLevelIndex;
  19. extern    int    NOBYTELEVEL;
  20. extern    int    OPTIMIZEBYTELEVEL;
  21. extern    int    RegionLimit;
  22. extern    int    PRINTINDEXLINE;
  23. extern    struct offsets **src_offset_table;
  24. extern    unsigned int    *multi_dest_index_set[MAXNUM_PAT];
  25. extern    struct offsets **multi_dest_offset_table[MAXNUM_PAT];
  26. extern    char    *index_argv[MAX_ARGS];
  27. extern    int    index_argc;
  28. extern    CHAR    GProgname[MAXNAME];
  29. extern    FILE    *indexfp, *minifp;
  30. extern int REAL_PARTITION, REAL_INDEX_BUF, MAX_ALL_INDEX, FILEMASK_SIZE;
  31. extern int p_table[MAX_PARTITION];
  32. extern int GNumpartitions;
  33. extern    int    INVERSE;    /* agrep's global: need here to implement ~ in index-search */
  34.  
  35. free_list(p1)
  36.     struct offsets     **p1;
  37. {
  38.     struct offsets    *tp1;
  39.  
  40.     while (*p1 != NULL) {
  41.         tp1 = *p1;
  42.         *p1 = (*p1)->next;
  43.         my_free(tp1, sizeof(struct offsets));
  44.     }
  45. }
  46.  
  47. /* Unions offset lists list2 with list1 sorted in increasing order (deletes elements from list2) => changes both list1 and list2: f += #elems added */
  48. sorted_union(list1, list2, f, pf, cf)
  49.     struct offsets **list1, **list2;
  50.     int    *f, pf, cf;
  51. {
  52.     register struct offsets **p1 = list1, *p2;
  53.     register int    count = *f;    /* don't update *f if setting NOBYTELEVEL */
  54.  
  55.     if (NOBYTELEVEL) {    /* cannot come here! */
  56.         free_list(list1);
  57.         free_list(list2);
  58.         return;
  59.     }
  60.     if ( ((pf > MIN_OCCURRENCES)  && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE) ||
  61.          ((count > MIN_OCCURRENCES) && (pf > MAX_UNION * count)) || (pf > MAX_ABSOLUTE) ) {
  62.         /* enough if we check the second condition at the beginning since it won't surely be satisfied after this when count ++ */
  63.         NOBYTELEVEL = 1;
  64.         return;
  65.     }
  66.     while (*list2 != NULL) {
  67.         /* extract 1st element, update list2 */
  68.         p2 = *list2;
  69.         *list2 = (*list2)->next;
  70.         p2->next = NULL;
  71.  
  72.         /* find position to insert p2, and do so */
  73.         p1 = list1;
  74.         while (((*p1) != NULL) && ((*p1)->offset < p2->offset)) p1 = &(*p1)->next;
  75.         if (*p1 == NULL) {    /* end of list1: append list2 to it and return */
  76.             *p1 = p2;
  77.             p2->next = *list2;
  78.             *list2 = NULL;
  79.             if (cf > 0)  count = *f + cf;
  80.             if ( ((pf > MIN_OCCURRENCES) && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE)) {
  81.                 NOBYTELEVEL = 1;
  82.                 return;
  83.             }
  84.             *f = count;
  85.             return;
  86.         }
  87.         else if (p2->offset == (*p1)->offset) my_free(p2, sizeof(struct offsets));
  88.         else {
  89.             p2->next = *p1;
  90.             *p1 = p2;
  91.             count ++;
  92.             if ( ((pf > MIN_OCCURRENCES)  && (count > MAX_UNION * pf)) || (count > MAX_ABSOLUTE) ) {
  93.                 NOBYTELEVEL = 1;
  94.                 return;
  95.             }
  96.             /* update list1 */
  97.             list1 = &(*p1)->next;
  98.         }
  99.     }
  100.     *f = count;
  101. }
  102.  
  103. /* Intersects offset lists list2 with list1 sorted in increasing order (deletes elements from list2) => changes both list1 and list2 */
  104. sorted_intersection(filenum, list1, list2, f)
  105.     struct offsets **list1, **list2;
  106.     int    *f;
  107. {
  108.     register struct offsets **p1 = list1, *p2, *tp1;
  109.     register int diff;
  110.  
  111.     if (NOBYTELEVEL) {    /* cannot come here! */
  112.         free_list(list1);
  113.         free_list(list2);
  114.         return;
  115.     }
  116.  
  117.     /* find position to intersect list2, and do so: REMEBER: list1 is in increasing order, and so is list2 !!! */
  118.     p1 = list1;
  119.     while ( ((*p1) != NULL) && (*list2 != NULL) ) {
  120.         diff = (*list2)->offset - (*p1)->offset;
  121.         if ( (diff >= -RegionLimit) && (diff <= RegionLimit) ) {
  122.             (*p1)->done = 1; /* p1 is in */
  123.             p1 = &(*p1)->next;
  124.             /* Can't increment p2 here since it might keep others after p1 also in */
  125.         }
  126.         else {
  127.             if (diff < 0) {
  128.                 p2 = *list2;
  129.                 *list2 = (*list2)->next;
  130.                 my_free(p2, sizeof(struct offsets));
  131.                 /* p1 can intersect with list2's next */
  132.             }
  133.             else {
  134.                 if((*p1)->done) p1 = &(*p1)->next; /* imposs */
  135.                 else {
  136.                     tp1 = *p1;
  137.                     *p1 = (*p1)->next;
  138.                     my_free(tp1, sizeof(struct offsets));
  139.                     (*f) --;
  140.                 }
  141.                 /* list2 can intersect with p1's next */
  142.             }
  143.         }
  144.     }
  145.  
  146.     while (*list2 != NULL) {
  147.         p2 = *list2;
  148.         *list2 = (*list2)->next;
  149.         my_free(p2, sizeof(struct offsets));
  150.     }
  151.  
  152.     p1 = list1;
  153.     while (*p1 != NULL) {
  154.         if ((*p1)->done == 0) {
  155.             tp1 = *p1;
  156.             *p1 = (*p1)->next;
  157.             my_free(tp1, sizeof(struct offsets));
  158.             (*f) --;
  159.         }
  160.         else {
  161.             (*p1)->done = 0;    /* for the next round! */
  162.             p1 = &(*p1)->next;
  163.         }
  164.     }
  165. }
  166.  
  167. purge_offsets(p1)
  168.     struct offsets **p1;
  169. {
  170.     struct offsets *tp1;
  171.  
  172.     while (*p1 != NULL) {
  173.         if ((*p1)->sign == 0) {
  174.             tp1 = *p1;
  175.             (*p1) = (*p1)->next;
  176.             my_free(tp1, sizeof(struct offsets));
  177.         }
  178.         else p1 = &(*p1)->next;
  179.     }
  180. }
  181.  
  182. /* Returns 1 if it is a Universal set, 0 otherwise. Constraint: WORD_END_MARK/ALL_INDEX_MARK must occur at or after buffer[0] */
  183. get_set(buffer, set, offset_table, patlen, pattern, patattr, outfile, partfp, frequency, prevfreq)
  184.     unsigned char    *buffer;
  185.     unsigned int    *set;
  186.     struct offsets **offset_table;
  187.     int    patlen;
  188.     char    *pattern;
  189.     int    patattr;
  190.     FILE    *outfile;
  191.     FILE    *partfp;
  192.     int    *frequency, prevfreq;
  193. {
  194.     int    bdx2, j;
  195.     int    ret;
  196.     int    x=0, y=0, diff, even_words=1, prevy;
  197.     int    indexattr = 0;
  198.     struct offsets *o, *tailo, *heado;
  199.     int    delim = encode8b(0);
  200.     int    curfreq = 0;
  201.     unsigned char c;
  202.  
  203.     /* buffer[0] is '\n', search must start from buffer[1] */
  204.     bdx2 = 1;
  205.     if (OneFilePerBlock)
  206.         while((bdx2<REAL_INDEX_BUF+1) && (buffer[bdx2] != WORD_END_MARK) && (buffer[bdx2] != ALL_INDEX_MARK)) bdx2++;
  207.     else while((bdx2<REAL_INDEX_BUF+1) && (buffer[bdx2] != WORD_END_MARK)) bdx2++;
  208.     if (bdx2 >= REAL_INDEX_BUF+1) return 0;
  209.     if (StructuredIndex) {
  210.         if (StructuredIndex < MaxNum8bPartition - 1) {
  211.             indexattr = decode8b(buffer[bdx2+1]);
  212.         }
  213.         else {
  214.             indexattr = decode16b((buffer[bdx2+1] << 8) | (buffer[bdx2 + 2]));
  215.         }
  216.         /* printf("i=%d p=%d\n", indexattr, patattr); */
  217.         if ((patattr > 0) && (indexattr != patattr)) {
  218. #if    BG_DEBUG
  219.             fprintf(debug, "indexattr=%d DOES NOT MATCH patattr=%d\n", indexattr, patattr);
  220. #endif    /*BG_DEBUG*/
  221.             return 0;
  222.         }
  223.     }
  224.     if (PRINTINDEXLINE) {
  225.         c = buffer[bdx2];
  226.         buffer[bdx2] = '\0';
  227.         printf("%s %d", &buffer[1], indexattr);
  228.         buffer[bdx2] = c;
  229.         if (c == ALL_INDEX_MARK) printf(" ! ");
  230.         else printf(" : ");
  231.     }
  232.  
  233.     if (OneFilePerBlock && (buffer[bdx2] == ALL_INDEX_MARK)) {
  234.         /* A intersection Univ-set = A: so src_index_set won't change; A union Univ-set = Univ-set: so src_index_set = all 1s */
  235. #if    BG_DEBUG
  236.         buffer[bdx2] = '\0';
  237.         fprintf(debug, "All indices search for %s\n", buffer + 1);
  238.         buffer[bdx2] = ALL_INDEX_MARK;
  239. #endif    /*BG_DEBUG*/
  240.         set[REAL_PARTITION - 1] = 1;
  241.         for(bdx2=0; bdx2<round(OneFilePerBlock, 8*sizeof(int)) - 1; bdx2++) {
  242.             set[bdx2] = 0xffffffff;
  243.         }
  244.         set[bdx2] = 0;
  245.         for (j=0; j<8*sizeof(int); j++) {
  246.             if (bdx2*8*sizeof(int) + j >= OneFilePerBlock) break;
  247.             set[bdx2] |= mask_int[j];
  248.         }
  249.         if (ByteLevelIndex) NOBYTELEVEL = 1;
  250.         return 1;
  251.     }
  252.     else if (!OneFilePerBlock) {    /* check only if index+partitions are NOT split */
  253. #if    BG_DEBUG
  254.         buffer[bdx2] = '\0';
  255.         fprintf(debug, "memagrep-line: %s\t\tpattern: %s\n", buffer, pattern);
  256. #endif    /*BG_DEBUG*/
  257.         /* ignore if pattern with all its options matches block number sequence: bg+udi: Feb/16/93 */
  258.         buffer[bdx2] = '\n';    /* memagrep needs buffer to end with '\n' */
  259.         if ((ret = memagrep_search(patlen, pattern, bdx2+1, buffer, 0, outfile)) <= 0) return 0;
  260.         else buffer[bdx2] = WORD_END_MARK;
  261.     }
  262.     if ((StructuredIndex > 0) && (StructuredIndex < MaxNum8bPartition - 1)) bdx2 ++;
  263.     else if (StructuredIndex > 0) bdx2 += 2;
  264.     bdx2++;    /* bdx2 now points to the first byte of the offset */
  265.  
  266.     even_words = 1;
  267.     /* Code identical to that in merge_in() in glimpseindex */
  268.     if (OneFilePerBlock) {
  269.         get_block_numbers(&buffer[bdx2], &buffer[bdx2], partfp);
  270.         while((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0')) {
  271.         /* First get the file name */
  272.         x = 0;
  273.         if (ByteLevelIndex) {
  274.             if (OneFilePerBlock <= MaxNum8bPartition) {
  275.             x = decode8b(buffer[bdx2]);
  276.             bdx2 ++;
  277.             }
  278.             else if (OneFilePerBlock <= MaxNum16bPartition) {
  279.             x = (buffer[bdx2] << 8) | buffer[bdx2+1];
  280.             x = decode16b(x);
  281.             bdx2 += 2;
  282.             }
  283.             else {
  284.             x = (buffer[bdx2] << 16) | (buffer[bdx2+1] << 8) | buffer[bdx2+2];
  285.             x = decode24b(x);
  286.             bdx2 += 3;
  287.             }
  288.         }
  289.         else if (OneFilePerBlock <= MaxNum8bPartition) {
  290.             x = decode8b(buffer[bdx2]);
  291.             bdx2 ++;
  292.         }
  293.         else if (OneFilePerBlock <= MaxNum12bPartition) {
  294.             if (even_words) {
  295.             x = ((buffer[bdx2+1] & 0x0000000f) << 8) | buffer[bdx2];
  296.             x = decode12b(x);
  297.             bdx2 += 2;
  298.             even_words = 0;
  299.             }
  300.             else {    /* odd number of words so far */
  301.             x = ((buffer[bdx2-1] & 0x000000f0) << 4) | buffer[bdx2];
  302.             x = decode12b(x);
  303.             bdx2 ++;
  304.             even_words = 1;
  305.             }
  306.         }
  307.         else if (OneFilePerBlock <= MaxNum16bPartition) {
  308.             x = (buffer[bdx2] << 8) | buffer[bdx2+1];
  309.             x = decode16b(x);
  310.             bdx2 += 2;
  311.         }
  312.         else {
  313.             x = (buffer[bdx2] << 16) | (buffer[bdx2+1] << 8) | buffer[bdx2+2];
  314.             x = decode24b(x);
  315.             bdx2 += 3;
  316.         }
  317.         set[block2index(x)] |= block2mask(x);
  318.         if (PRINTINDEXLINE) {
  319.             printf("%d [", x);
  320.         }
  321.  
  322.         prevy = 0;
  323.         if (ByteLevelIndex) {
  324.             heado = tailo = NULL;
  325.             curfreq = 0;
  326.             while ((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0')) {
  327.             y = decode8b(buffer[bdx2]);
  328.             if ((y & 0x000000c0) == 0) {    /* one byte offset */
  329.                 diff = y&0x0000003f;
  330.                 y = prevy + diff;
  331.                 bdx2 ++;
  332.             }
  333.             else if ((y & 0x000000c0) == 0x40) {    /* two byte offset */
  334.                 diff = decode8b(buffer[bdx2+1]);
  335.                 y = prevy + (((y & 0x0000003f) * MaxNum8bPartition) + diff);
  336.                 bdx2 += 2;
  337.             }
  338.             else if ((y & 0x000000c0) == 0x80) {    /* three byte offset */
  339.                 diff = decode16b((buffer[bdx2+1] << 8) | buffer[bdx2+2]);
  340.                 y = prevy + (((y & 0x0000003f) * MaxNum16bPartition) + diff);
  341.                 bdx2 += 3;
  342.             }
  343.             else {    /* four byte offset */
  344.                 diff = decode24b((buffer[bdx2+1] << 16) | (buffer[bdx2+2] << 8) | buffer[bdx2+3]);
  345.                 y = prevy + (((y & 0x0000003f) * MaxNum24bPartition) + diff);
  346.                 bdx2 += 4;
  347.             }
  348.             prevy = y;
  349.             if (PRINTINDEXLINE) {
  350.                 printf(" %d", y);
  351.             }
  352.  
  353.             curfreq ++;
  354.  
  355.             if (!(Only_first && !PRINTAPPXFILEMATCH) && !NOBYTELEVEL &&    /* below borrowed from sorted_union */
  356.                 !(((prevfreq>MIN_OCCURRENCES)&&(curfreq+*frequency > MAX_UNION*prevfreq)) || (curfreq+*frequency > MAX_ABSOLUTE))) {
  357.                 /* These o's will be in sorted order. Just collect all of them and merge with &offset_table[x]. */
  358.                 o = (struct offsets *)my_malloc(sizeof(struct offsets));
  359.                 o->offset = y;
  360.                 o->next = NULL;
  361.                 o->sign = o->done = 0;
  362.                 if (heado == NULL) {
  363.                 heado = o;
  364.                 tailo = o;
  365.                 }
  366.                 else {
  367.                 tailo->next = o;
  368.                 tailo = o;
  369.                 }
  370.             }
  371.             else {
  372.                 if (heado != NULL) free_list(&heado);
  373.                 /* printf("1 "); */
  374.                 NOBYTELEVEL = 1;    /* can't return since have to or the bitmasks */
  375.             }
  376.             if ((bdx2<REAL_INDEX_BUF) && (buffer[bdx2] == delim)) {    /* look at offsets corr. to a new file now */
  377.                 bdx2 ++;
  378.                 break;
  379.             }
  380.             }
  381.  
  382.             if (heado == NULL) *frequency += curfreq;
  383.             else if (!(Only_first && !PRINTAPPXFILEMATCH) && !NOBYTELEVEL) {
  384.             sorted_union(&offset_table[x], &heado, frequency, prevfreq, curfreq);    /* this will free heado's elements and ++ *frequency */
  385.             if (NOBYTELEVEL) *frequency += curfreq;    /* can't return since have to or the bitmasks */
  386.             if (heado != NULL) free_list(&heado);
  387.             }
  388.         }
  389.  
  390.         if (PRINTINDEXLINE) {
  391.             printf("] ");
  392.         }
  393.         }
  394.     }
  395.     else {
  396.         while((bdx2<MAX_INDEX_BUF) && (buffer[bdx2] != '\n') && (buffer[bdx2] != '\0') && (buffer[bdx2] < MAX_PARTITION)) {
  397.         if (PRINTINDEXLINE) {
  398.             for (j=p_table[buffer[bdx2]]; j<p_table[buffer[bdx2] + 1]; j++)
  399.             printf("%d [] ", j);
  400.         }
  401.         set[buffer[bdx2]] = 1;
  402.         bdx2++;
  403.         }
  404.     }
  405.     if (PRINTINDEXLINE) {
  406.         printf("\n");
  407.     }
  408.     return 0;
  409. }
  410.  
  411. /*
  412.  * This is a very simple function: it gets the list of matched lines from the index,
  413.  * and sets the block numbers corr. to files that need to be searched in "index_tab".
  414.  * It also sets the file-offsets that have to be searched in "offset_tab" (byte-level).
  415.  */
  416. get_index(infile, index_tab, offset_tab, pattern, patlen, patattr, index_argv, index_argc, outfile, partfp, parse, first_time)
  417. char *infile;
  418. unsigned int  *index_tab;
  419. struct offsets **offset_tab;
  420. char *pattern;
  421. int patlen;
  422. int patattr;
  423. char *index_argv;
  424. int index_argc;
  425. FILE *outfile;
  426. FILE *partfp;
  427. int parse;
  428. int first_time;
  429. {
  430.     int  i=0, j, iii;
  431.     FILE *f_in;
  432.     struct offsets **offsetptr = multi_dest_offset_table[0];    /* cannot be NULL if ByteLevelIndex: main.c takes care of that */
  433.     int ret=0;
  434.  
  435.     if (OneFilePerBlock && (parse & OR_EXP) && (index_tab[REAL_PARTITION - 1] == 1)) return 0;
  436.     if (((infile == NULL) || !strcmp(infile, "")) /* || (index_tab == NULL) || (offset_tab == NULL) || (pattern == NULL)*/) return -1;
  437.     if((f_in = fopen(infile, "r")) == NULL) {
  438.         fprintf(stderr, "%s: can't open for reading: %s/%s\n", GProgname, INDEX_DIR, infile);
  439.         return -1;
  440.     }
  441.     if (OneFilePerBlock)
  442.         for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) {
  443.                 dest_index_set[i] = 0;
  444.         }
  445.     else for(i=0; i<MAX_PARTITION; i++) {
  446.                 dest_index_set[i] = 0;
  447.         }
  448.     dest_index_buf[0] = '\n';    /* memagrep needs buffer to begin with '\n' */
  449.  
  450.     dest_index_set[REAL_PARTITION - 2] = 0;
  451.     while(fgets(dest_index_buf+1, REAL_INDEX_BUF, f_in)) {
  452. #if    BG_DEBUG
  453.         fprintf(debug, "index-line: %s", dest_index_buf+1);
  454. #endif    /*BG_DEBUG*/
  455.         if ((ret = get_set(&dest_index_buf[0], dest_index_set, offsetptr, patlen, pattern, patattr, outfile, partfp, &dest_index_set[REAL_PARTITION - 2], index_tab[REAL_PARTITION - 2])) != 0)
  456.             break;    /* all index mark touched */
  457.     }
  458.     if (NOBYTELEVEL) {
  459.         for (iii=0; iii<OneFilePerBlock; iii++) {
  460.         free_list(&offset_tab[iii]);
  461.         free_list(&offsetptr[iii]);
  462.         }
  463.     }
  464.  
  465.     if (INVERSE) {
  466.         if (OneFilePerBlock) {
  467.         if (ByteLevelIndex) NOBYTELEVEL = 1;    /* can't collect all offsets where pattern DOES NOT occur! */
  468.         for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) dest_index_set[i] = ~dest_index_set[i];
  469.         for (j=0; j<8*sizeof(int); j++) {
  470.             if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  471.             if (dest_index_set[i] & mask_int[j]) dest_index_set[i] &= ~mask_int[j];
  472.             else dest_index_set[i] |= mask_int[j];
  473.         }
  474.         }
  475.         else {
  476.         for(i=0; i<MAX_PARTITION; i++) {
  477.             if (i>=GNumpartitions-1) break;    /* STUPID: get_table returns 1 + part_num, where part_num was no. of partitions glimpseindex found */
  478.             if ((i == 0) || (i == '\n')) continue;
  479.             if (dest_index_set[i]) dest_index_set[i] = 0;
  480.             else dest_index_set[i] = 1;
  481.         }
  482.         }
  483.     }
  484.  
  485.     /* Take intersection if parse=ANDPAT or 0 (one terminal pattern), union if OR_EXP; Take care of universal sets in index_tab[REAL_PARTITION - 1] */
  486.     if (OneFilePerBlock) {
  487.         if (parse & OR_EXP) {
  488.         if (ret) {
  489.         ret_is_1:
  490.             index_tab[REAL_PARTITION - 1] = 1;
  491.             for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  492.             index_tab[i] = 0xffffffff;
  493.             }
  494.             index_tab[i] = 0;
  495.             for (j=0; j<8*sizeof(int); j++) {
  496.             if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  497.             index_tab[i] |= mask_int[j];
  498.             }
  499.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) for (i=0; i<OneFilePerBlock; i++) {
  500.             free_list(&offsetptr[i]);
  501.             free_list(&offset_tab[i]);
  502.             }
  503.             if (ByteLevelIndex) NOBYTELEVEL = 1;
  504.             fclose(f_in);
  505.             return 0;
  506.         }
  507.         index_tab[REAL_PARTITION - 1] = 0;
  508.         for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] |= dest_index_set[i];
  509.         if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  510.             for (i=0; i<OneFilePerBlock; i++) {
  511.             sorted_union(&offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2], dest_index_set[REAL_PARTITION - 2], 0);
  512.             if (NOBYTELEVEL) {
  513.                 for (iii=0; iii<OneFilePerBlock; iii++) {
  514.                 free_list(&offset_tab[iii]);
  515.                 free_list(&offsetptr[iii]);
  516.                 }
  517.                 break;
  518.             }
  519.             }
  520.         }
  521.         }
  522.         else {
  523.         if (((index_tab[REAL_PARTITION - 1] == 1) || first_time) && (ret)) {
  524.         both_are_1:
  525.             if (first_time) {
  526.             index_tab[REAL_PARTITION - 1] = 1;
  527.             for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  528.                 index_tab[i] = 0xffffffff;
  529.             }
  530.             index_tab[i] = 0;
  531.             for (j=0; j<8*sizeof(int); j++) {
  532.                 if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  533.                 index_tab[i] |= mask_int[j];
  534.             }
  535.             }
  536.             first_time = 0;
  537.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) for (i=0; i<OneFilePerBlock; i++) {
  538.             free_list(&offsetptr[i]);
  539.             free_list(&offset_tab[i]);
  540.             }
  541.             if (ByteLevelIndex) NOBYTELEVEL = 1;
  542.             /*
  543.             fclose(f_in);
  544.             return 0;
  545.             */
  546.         }
  547.         else if ((index_tab[REAL_PARTITION - 1] == 1) || first_time) {
  548.             first_time = 0;
  549.             index_tab[REAL_PARTITION - 1] = 0;
  550.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] = dest_index_set[i];
  551.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  552.             for (i=0; i<OneFilePerBlock; i++) {
  553.                 free_list(&offset_tab[i]);
  554.                 offset_tab[i] = offsetptr[i];
  555.                 offsetptr[i] = NULL;
  556.             }
  557.             }
  558.         }
  559.         else if (ret) {
  560.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) for (i=0; i<OneFilePerBlock; i++) free_list(&offsetptr[i]);
  561.         }
  562.         else {
  563.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] &= dest_index_set[i];
  564.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  565.             if (first_time || WHOLEFILESCOPE) {
  566.                 first_time = 0;
  567.                 for (i=0; i<OneFilePerBlock; i++) {
  568.                 sorted_union(&offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2], dest_index_set[REAL_PARTITION - 2], 0);
  569.                 if (NOBYTELEVEL) {
  570.                     for (iii=0; iii<OneFilePerBlock; iii++) {
  571.                     free_list(&offset_tab[iii]);
  572.                     free_list(&offsetptr[iii]);
  573.                     }
  574.                     break;
  575.                 }
  576.                 }
  577.             }
  578.             else {
  579.                 for (i=0; i<OneFilePerBlock; i++) {
  580.                 if ((index_tab[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  581.                     sorted_intersection(i, &offset_tab[i], &offsetptr[i], &index_tab[REAL_PARTITION - 2]);
  582.                 else free_list(&offsetptr[i]);
  583.                 /*
  584.                 if (index_tab[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  585.                     if (!NOBYTELEVEL) {
  586.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  587.                         free_list(&offset_tab[iii]);
  588.                         free_list(&offsetptr[iii]);
  589.                         }
  590.                     }
  591.                     NOBYTELEVEL = 1;
  592.                     OPTIMIZEBYTELEVEL = 1;
  593.                     break;
  594.                 }
  595.                 */
  596.                 }
  597.             }
  598.             }
  599.         }
  600.         }
  601.     }
  602.     else {
  603.         if (parse & OR_EXP)
  604.         for(i=0; i<MAX_PARTITION; i++) index_tab[i] |= dest_index_set[i];
  605.         else
  606.         for(i=0; i<MAX_PARTITION; i++) index_tab[i] &= dest_index_set[i];
  607.     }
  608.  
  609. #if    BG_DEBUG
  610.     fprintf(debug, "get_index(): the following partitions are ON\n");
  611.     for(i=0; i<((OneFilePerBlock > 0) ? round(OneFilePerBlock, 8*sizeof(int)) : MAX_PARTITION); i++) {
  612.           if(index_tab[i]) fprintf(debug, "%d,%x\n", i, index_tab[i]);
  613.     }
  614. #endif    /*BG_DEBUG*/
  615.  
  616.     fclose(f_in);
  617.     return 0;
  618. }
  619.  
  620. /*
  621.  * Same as above, but uses mgrep to search the index for many patterns at one go,
  622.  * and interprets the output obtained from the -M and -P options (set in main.c).
  623.  */
  624. mgrep_get_index(infile, index_tab, offset_tab, pat_list, pat_lens, pat_attr, mgrep_pat_index, num_mgrep_pat, patbufpos, index_argv, index_argc, outfile, partfp, parse, first_time)
  625. char *infile;
  626. int  *index_tab;
  627. struct offsets **offset_tab;
  628. char *pat_list[];
  629. int pat_lens[];
  630. int pat_attr[];
  631. int mgrep_pat_index[];
  632. int num_mgrep_pat;
  633. int patbufpos;
  634. char *index_argv[];
  635. int index_argc;
  636. FILE *outfile;
  637. FILE *partfp;
  638. int parse;
  639. int first_time;
  640. {
  641.     int  i=0, j, temp, iii, jjj;
  642.     FILE *f_in;
  643.     int ret;
  644.     int x=0, y=0, even_words=1;
  645.     int patnum;
  646.     unsigned int *setptr;
  647.     struct offsets **offsetptr;
  648.     CHAR dummypat[MAX_PAT];
  649.     int  dummylen=0;
  650.     char  allindexmark[MAXNUM_PAT];
  651.     int k;
  652.     int sorted[MAXNUM_PAT], min, max;
  653.  
  654.     if (OneFilePerBlock && (parse & OR_EXP) && (index_tab[REAL_PARTITION - 1] == 1)) return 0;
  655.     /* Do the mgrep() */
  656.     if ((f_in = fopen(infile, "w")) == NULL) {
  657.         fprintf(stderr, "%s: run out of file descriptors!\n", GProgname);
  658.         return -1;
  659.     }
  660.     errno = 0;
  661.     if ((ret = fileagrep(index_argc, index_argv, 0, f_in)) < 0) {
  662.         fprintf(stderr, "%s: error in searching index\n", HARVEST_PREFIX);
  663.         fclose(f_in);
  664.         return -1;
  665.     }
  666.     fflush(f_in);
  667.     fclose(f_in);
  668.     f_in = NULL;
  669.  
  670.     index_argv[patbufpos] = NULL;
  671.     /* For index-search with memgrep and get-filenames */
  672.     dummypat[0] = '\0';
  673.     if ((dummylen = memagrep_init(index_argc, index_argv, MAX_PAT, dummypat)) <= 0) {
  674.         fclose(f_in);
  675.         return -1;
  676.     }
  677.  
  678.     /* Interpret the result */
  679.     if((f_in = fopen(infile, "r")) == NULL) {
  680.         fprintf(stderr, "%s: can't open for reading: %s/%s\n", GProgname, INDEX_DIR, infile);
  681.         return -1;
  682.     }
  683.     if (OneFilePerBlock) {
  684.         for (patnum=0; patnum<num_mgrep_pat; patnum ++) {
  685.         for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) {
  686.             multi_dest_index_set[patnum][i] = 0;
  687.         }
  688.         if (ByteLevelIndex) for(i=0; i<OneFilePerBlock; i++) {
  689.             free_list(&multi_dest_offset_table[patnum][i]);
  690.             /* multi_dest_offset_table[patnum][i] = NULL; bg, 28/9/1995 */
  691.         }
  692.         multi_dest_index_set[patnum][REAL_PARTITION - 1] = 0;
  693.         multi_dest_index_set[patnum][REAL_PARTITION - 2] = 0;
  694.         }
  695.     }
  696.     else {
  697.         for (patnum=0; patnum<num_mgrep_pat; patnum ++)
  698.         for(i=0; i<MAX_PARTITION; i++) {
  699.                     multi_dest_index_set[patnum][i] = 0;
  700.         }
  701.     }
  702.     dest_index_buf[0] = '\n';    /* memagrep needs buffer to begin with '\n' */
  703.  
  704.     memset(allindexmark, '\0', num_mgrep_pat);
  705.     min = (index_tab[REAL_PARTITION - 1] == 1) ? 0 : index_tab[REAL_PARTITION - 2];
  706.     while(fgets(dest_index_buf+1, REAL_INDEX_BUF, f_in)) {
  707.         patnum=0;
  708.         sscanf(&dest_index_buf[1], "%d-", &patnum);
  709. #if    BG_DEBUG
  710.         fprintf(debug, "patnum=%d len=%d pat=%s attr=%d index-line: %s\n", patnum, pat_lens[mgrep_pat_index[patnum-1]], pat_list[mgrep_pat_index[patnum-1]], pat_attr[mgrep_pat_index[patnum-1]], dest_index_buf+1);
  711. #endif    /*BG_DEBUG*/
  712.         if ((patnum < 1) || (patnum > num_mgrep_pat)) continue;    /* error! */
  713.         setptr = multi_dest_index_set[patnum - 1];
  714.         offsetptr = multi_dest_offset_table[patnum - 1];
  715.         for(k=0; dest_index_buf[k] != ' '; k++);
  716.         dest_index_buf[k] = '\n';
  717.         if (!allindexmark[patnum - 1])
  718.             allindexmark[patnum - 1] = (char)get_set(&dest_index_buf[k], setptr, offsetptr, pat_lens[mgrep_pat_index[patnum-1]],
  719.                                 pat_list[mgrep_pat_index[patnum-1]], pat_attr[mgrep_pat_index[patnum-1]], outfile, partfp,
  720.                                 &setptr[REAL_PARTITION - 2], min);
  721.         /* To test the maximum disparity to stop unions within above */
  722.         if (!allindexmark[patnum-1]) min = setptr[REAL_PARTITION - 2];
  723.         for (patnum=0; patnum<num_mgrep_pat; patnum ++) {
  724.             if ((multi_dest_index_set[patnum][REAL_PARTITION - 2] < min) && (multi_dest_index_set[patnum][REAL_PARTITION - 1] != 1))
  725.                 min = multi_dest_index_set[patnum][REAL_PARTITION - 2];
  726.         }
  727.         min += (index_tab[REAL_PARTITION - 1] == 1) ? 0 : index_tab[REAL_PARTITION - 2];
  728.     }
  729. #if    0
  730.     for (patnum=0; patnum<num_mgrep_pat; patnum++)
  731.         printf("%d=%d,%d\n", patnum, multi_dest_index_set[patnum][REAL_PARTITION - 1], multi_dest_index_set[patnum][REAL_PARTITION - 2]);
  732. #endif    /*0*/
  733.  
  734.     for (patnum=0; patnum<num_mgrep_pat; patnum++)
  735.         sorted[patnum] = patnum;
  736.     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  737.         max = 0;
  738.         for (patnum=1; patnum<num_mgrep_pat; patnum++) {
  739.             if (multi_dest_index_set[patnum][REAL_PARTITION - 2] > multi_dest_index_set[max][REAL_PARTITION - 2])
  740.             max = patnum;
  741.         }
  742.         /* Sort them according to the lengths of the lists in increasing order: min first */
  743.         for (patnum=0; patnum<num_mgrep_pat; patnum++) {
  744.             min = patnum;
  745.             for (j=patnum+1; j<num_mgrep_pat; j++)
  746.             if (multi_dest_index_set[sorted[j]][REAL_PARTITION - 2] < multi_dest_index_set[sorted[min]][REAL_PARTITION - 2])
  747.                 min = j;
  748.             if (min != patnum) {
  749.             temp = sorted[patnum];
  750.             sorted[patnum] = sorted[min];
  751.             sorted[min] = temp;
  752.             }
  753.         }
  754.         if (multi_dest_index_set[sorted[max]][REAL_PARTITION - 2] > MAX_DISPARITY * multi_dest_index_set[sorted[0]][REAL_PARTITION - 2]) {
  755.             NOBYTELEVEL = 1;
  756.             /* printf("4 "); */
  757.             for (iii=0; iii<OneFilePerBlock; iii++) {
  758.             for (jjj=0; jjj<num_mgrep_pat; jjj++)
  759.                 free_list(&multi_dest_offset_table[jjj][iii]);
  760.             free_list(&offset_tab[iii]);
  761.             }
  762.         }
  763.     }
  764.     else if (NOBYTELEVEL) {
  765.         for (iii=0; iii<OneFilePerBlock; iii++) {
  766.         for (jjj=0; jjj<num_mgrep_pat; jjj++)
  767.             free_list(&multi_dest_offset_table[jjj][iii]);
  768.         free_list(&offset_tab[iii]);
  769.         }
  770.     }
  771.  
  772.     /* Take intersection if parse=ANDPAT or 0 (one terminal pattern), union if OR_EXP; Take care of universal sets in offset_tab[REAL_PARTITION - 1] */
  773.     for (patnum=0; patnum<num_mgrep_pat; patnum++) {
  774.         if (OneFilePerBlock) {
  775.             if (parse & OR_EXP) {
  776.             if (allindexmark[sorted[patnum]]) {
  777.             ret_is_1:
  778.                 index_tab[REAL_PARTITION - 1] = 1;
  779.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  780.                 index_tab[i] = 0xffffffff;
  781.                 }
  782.                 index_tab[i] = 0;
  783.                 for (j=0; j<8*sizeof(int); j++) {
  784.                 if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  785.                 index_tab[i] |= mask_int[j];
  786.                 }
  787.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH))
  788.                   for (i=0; i<OneFilePerBlock; i++) {
  789.                     for (patnum=0;patnum<num_mgrep_pat;patnum++)
  790.                   free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  791.                 free_list(&offset_tab[i]);
  792.                   }
  793.                 if (ByteLevelIndex) NOBYTELEVEL = 1;
  794.                 fclose(f_in);
  795.                 return 0;
  796.             }
  797.             index_tab[REAL_PARTITION - 1] = 0;
  798.             for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] |= multi_dest_index_set[sorted[patnum]][i];
  799.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  800.                 for (i=0; i<OneFilePerBlock; i++) {
  801.                 sorted_union(&offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2], multi_dest_index_set[sorted[patnum]][REAL_PARTITION - 2], 0);
  802.  
  803.                 if (NOBYTELEVEL) {
  804.                     for (iii=0; iii<OneFilePerBlock; iii++) {
  805.                     for (jjj=0; jjj<num_mgrep_pat; jjj++)
  806.                         free_list(&multi_dest_offset_table[jjj][iii]);
  807.                     free_list(&offset_tab[iii]);
  808.                     }
  809.                     break;
  810.                 }
  811.                 }
  812.             }
  813.             }
  814.             else {
  815.             if (((index_tab[REAL_PARTITION - 1] == 1) || first_time) && (allindexmark[sorted[patnum]])) {
  816.             both_are_1:
  817.                 if (first_time) {
  818.                 index_tab[REAL_PARTITION - 1] = 1;
  819.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  820.                     index_tab[i] = 0xffffffff;
  821.                 }
  822.                 index_tab[i] = 0;
  823.                 for (j=0; j<8*sizeof(int); j++) {
  824.                     if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  825.                     index_tab[i] |= mask_int[j];
  826.                 }
  827.                 }
  828.                 first_time = 0;
  829.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH))
  830.                   for (i=0; i<OneFilePerBlock; i++) {
  831.                     for (patnum=0;patnum<num_mgrep_pat;patnum++)
  832.                    free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  833.                  free_list(&offset_tab[i]);
  834.                   }
  835.                 if (ByteLevelIndex) NOBYTELEVEL = 1;
  836.                 /*
  837.                 fclose(f_in);
  838.                 return 0;
  839.                 */
  840.             }
  841.             else if ((index_tab[REAL_PARTITION - 1] == 1) || first_time) {
  842.                 first_time = 0;
  843.                 index_tab[REAL_PARTITION - 1] = 0;
  844.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] = multi_dest_index_set[sorted[patnum]][i];
  845.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  846.                 for (i=0; i<OneFilePerBlock; i++) {
  847.                     free_list(&offset_tab[i]);
  848.                     offset_tab[i] = multi_dest_offset_table[sorted[patnum]][i];
  849.                     multi_dest_offset_table[sorted[patnum]][i] = NULL;
  850.                 }
  851.                 }
  852.             }
  853.             else if (allindexmark[sorted[patnum]]) {
  854.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH))
  855.                   for (i=0; i<OneFilePerBlock; i++) free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  856.             }
  857.             else {
  858.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) index_tab[i] &= multi_dest_index_set[sorted[patnum]][i];
  859.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  860.                 if (first_time || WHOLEFILESCOPE) {
  861.                     first_time = 0;
  862.                     for (i=0; i<OneFilePerBlock; i++) {
  863.                     sorted_union(&offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2], multi_dest_index_set[sorted[patnum]][REAL_PARTITION - 2], 0);
  864.                     if (NOBYTELEVEL) {
  865.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  866.                         for (jjj=0; jjj<num_mgrep_pat; jjj++)
  867.                             free_list(&multi_dest_offset_table[jjj][iii]);
  868.                         free_list(&offset_tab[iii]);
  869.                         }
  870.                         break;
  871.                     }
  872.                     }
  873.                 }
  874.                 else {
  875.                     for (i=0; i<OneFilePerBlock; i++) {
  876.                     if ((index_tab[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  877.                         sorted_intersection(i, &offset_tab[i], &multi_dest_offset_table[sorted[patnum]][i], &index_tab[REAL_PARTITION - 2]);
  878.                     else free_list(&multi_dest_offset_table[sorted[patnum]][i]);
  879.                     /*
  880.                     if (index_tab[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  881.                         if (!NOBYTELEVEL) {
  882.                             for (iii=0; iii<OneFilePerBlock; iii++) {
  883.                             for (jjj=0; jjj<num_mgrep_pat; jjj++)
  884.                                 free_list(&multi_dest_offset_table[jjj][iii]);
  885.                             free_list(&offset_tab[iii]);
  886.                             }
  887.                         }
  888.                         NOBYTELEVEL = 1;
  889.                         OPTIMIZEBYTELEVEL = 1;
  890.                         break;
  891.                     }
  892.                     */
  893.                     }
  894.                 }
  895.                 }
  896.             }
  897.             }
  898.         }
  899.         else {
  900.             if (parse & OR_EXP) {
  901.             for (patnum=0; patnum<num_mgrep_pat; patnum++)
  902.                 for(i=0; i<MAX_PARTITION; i++) index_tab[i] |= multi_dest_index_set[patnum][i];
  903.             }
  904.             else {
  905.             for (patnum=0; patnum<num_mgrep_pat; patnum++)
  906.                 for(i=0; i<MAX_PARTITION; i++) index_tab[i] &= multi_dest_index_set[patnum][i];
  907.             }
  908.         }
  909.     }
  910.  
  911. #if    BG_DEBUG
  912.     fprintf(debug, "get_index(): the following partitions are ON\n");
  913.     for(i=0; i<((OneFilePerBlock > 0) ? round(OneFilePerBlock, 8*sizeof(int)) : MAX_PARTITION); i++) {
  914.           if(index_tab[i]) fprintf(debug, "%d,%x\n", i, index_tab[i]);
  915.     }
  916. #endif    /*BG_DEBUG*/
  917.  
  918.     fclose(f_in);
  919.     return 0;
  920. }
  921.  
  922. /* All borrowed from main.c and are needed for searching the index */
  923. extern    CHAR    *pat_list[MAXNUM_PAT];  /* complete words within global pattern */
  924. extern    int    pat_lens[MAXNUM_PAT];   /* their lengths */
  925. extern    int    pat_attr[MAXNUM_PAT];   /* set of attributes */
  926. extern    int    num_pat;
  927. extern    CHAR    pat_buf[(MAXNUM_PAT + 2)*MAXPAT];
  928. extern    int    pat_ptr;
  929. extern    int    is_mgrep_pat[MAXNUM_PAT];
  930. extern    int    mgrep_pat_index[MAXNUM_PAT];
  931. extern    int    num_mgrep_pat;
  932. extern    unsigned int    *src_index_set;
  933. extern    struct offsets **src_offset_table;
  934. extern    char    tempfile[];
  935. extern    int    patindex;
  936. extern    int    patbufpos;
  937. extern    ParseTree terminals[MAXNUM_PAT];
  938. extern    int    GBESTMATCH;        /* Should I change -B to -# where # = no. of errors? */
  939. extern    int    bestmatcherrors;    /* set during index search, used later on */
  940. extern    FILE    *partfp;        /* glimpse partitions */
  941. extern    FILE    *nullfp;        /* to discard output: agrep -s doesn't work properly */
  942. extern    int    ComplexBoolean;
  943. extern    int    num_terminals;
  944. #if    0
  945. extern  struct token *hash_table[MAX_64K_HASH];
  946. #else    /*0*/
  947. extern    int    mini_array_len;
  948. #endif    /*0*/
  949. extern  int    WORDBOUND, NOUPPER, D, LINENUM;
  950.  
  951. int
  952. veryfastsearch(argc, argv, num_pat, pat_list, pat_lens, minifp)
  953.     int    argc;
  954.     char    *argv[];
  955.     int    num_pat;
  956.     CHAR    *pat_list[MAXNUM_PAT];
  957.     int    pat_lens[MAXNUM_PAT];
  958.     FILE    *minifp;
  959. {
  960.     /*
  961.      * Figure out from options if very fast search is possible.
  962.      */
  963.     if (minifp == NULL) return 0;
  964.     if (!OneFilePerBlock) return 0;    /* you did not build index for speed anyway */
  965.     if (!(WORDBOUND && NOUPPER /*&& (D<=0)*/)) return 0;
  966.     if (LINENUM) return 0;
  967.     return 1;
  968.     /* if ((num_mgrep_pat == num_pat) || ((1 == num_pat) && (1 == checksg(pat_list[0], D, 0)))) return 1; */
  969.     /* either all >= 2 patterns are mgrep-able (simple) or there is just one simple pattern: i.e., "cast" can be used! */
  970.     /* return 0; */
  971. }
  972.  
  973. int
  974. mini_agrep(inword, inlen, outfp)
  975.     CHAR    *inword;
  976.     int    inlen;
  977.     FILE    *outfp;
  978. {
  979.     static struct stat st;
  980.     static    int statted = 0;
  981.     unsigned char    s[MAX_LINE_LEN], word[MAX_NAME_LEN];
  982.     long    beginoffset, endoffset, curroffset;
  983.     unsigned char c;
  984.     int    j, num = 0, cmp, len;
  985.  
  986.     if (!statted) {
  987.         sprintf((char*)s, "%s/%s", INDEX_DIR, INDEX_FILE);
  988.         if (stat(s, &st) == -1) {
  989.             fprintf(stderr, "Can't stat file: %s\n", s);
  990.             exit(2);
  991.         }
  992.         statted = 1;
  993.     }
  994.  
  995.     j = 0;
  996.     while (*inword) {
  997.         if (*inword == '\\') {
  998.             inword++;
  999.             continue;
  1000.         }
  1001.         if (isupper(*inword)) word[j] = tolower(*inword);
  1002.         else word[j] = *inword;
  1003.         j++;
  1004.         inword ++;
  1005.     }
  1006.     word[j] = '\0';
  1007.     len = j;
  1008.  
  1009.     if (!get_mini(word, len, &beginoffset, &endoffset, 0, mini_array_len, minifp)) return 0;
  1010.     if (endoffset == -1) endoffset = st.st_size;
  1011.     if (endoffset <= beginoffset) return 0;
  1012.  
  1013.     /* We must find all occurrences of the word (in all attributes) so can't quit when we find the first match */
  1014.     fseek(indexfp, beginoffset, 0);
  1015.     curroffset = ftell(indexfp);    /* = beginoffset */
  1016.     while ((curroffset < endoffset) && (fgets(s, MAX_LINE_LEN, indexfp) != NULL)) {
  1017.         j = 0;
  1018.         while ((j < MAX_LINE_LEN) && (s[j] != WORD_END_MARK) && (s[j] != ALL_INDEX_MARK) && (s[j] != '\0') && (s[j] != '\n')) j++;
  1019.         if ((j >= MAX_LINE_LEN) || (s[j] == '\0') || (s[j] == '\n')) {
  1020.             curroffset = ftell(indexfp);
  1021.             continue;
  1022.         }
  1023.         /* else it is WORD_END_MARK or ALL_INDEX_MARK */
  1024.         c = s[j];
  1025.         s[j] = '\0';
  1026.         cmp = strcmp(word, s);
  1027. #if    WORD_SORTED
  1028.         if (cmp < 0) break;    /* since index is sorted by word */
  1029.         else
  1030. #endif    /* WORD_SORTED */
  1031.         if (cmp != 0) {    /* not IDENTICALLY EQUAL */
  1032.             s[j] = c;
  1033.             curroffset = ftell(indexfp);
  1034.             continue;
  1035.         }
  1036.         s[j] = c;
  1037.         fputs(s, outfp);
  1038.         num++;
  1039.         curroffset = ftell(indexfp);
  1040.     }
  1041.     return num;
  1042. }
  1043.  
  1044. /* Returns the number of times a successful search was conducted: unused info at present. */
  1045. fillup_target(result_index_set, result_offset_table, parse)
  1046.     unsigned int    *result_index_set;
  1047.     struct offsets **result_offset_table;
  1048.     long    parse;
  1049. {
  1050.     int    i=0;
  1051.     FILE    *tmpfp;
  1052.     int    dummylen = 0;
  1053.     char    dummypat[MAX_PAT];
  1054.     int    successes = 0, ret;
  1055.     int    first_time = 1;
  1056.     int    veryfast = veryfastsearch(index_argc, index_argv, num_pat, pat_list, pat_lens, minifp);
  1057.     int    prev_INVERSE = INVERSE;
  1058.  
  1059.     while (i < num_pat)  {
  1060.         if (!veryfast) {
  1061.         if (is_mgrep_pat[i] && (num_mgrep_pat > 1)) {    /* do later */
  1062.             i++;
  1063.             continue;
  1064.         }
  1065.         strcpy(index_argv[patindex], pat_list[i]);    /* i-th pattern in its right position */
  1066.         }
  1067.         /* printf("pat_list[%d] = %s\n", i, pat_list[i]); */
  1068.  
  1069.         if ((tmpfp = fopen(tempfile, "w")) == NULL) {
  1070.             fprintf(stderr, "%s: cannot open for writing: %s, errno=%d\n", GProgname, tempfile, errno);
  1071.             return(-1);
  1072.         }
  1073.         errno = 0;
  1074.  
  1075.         if (veryfast && is_mgrep_pat[i]) {
  1076.             ret = mini_agrep(pat_list[i], pat_lens[i], tmpfp);
  1077.         }
  1078.         /* If this is the glimpse server, since the process doesn't die, most of its data pages might still remain in memory */
  1079.         else if ((ret = fileagrep(index_argc, index_argv, 0, tmpfp)) < 0) {
  1080.             /* reinitialization here takes care of agrep_argv changes AFTER split_pattern */
  1081.             fprintf(stderr, "%s: error in searching index\n", HARVEST_PREFIX);
  1082.             fclose(tmpfp);
  1083.             return(-1);
  1084.         }
  1085.         /* Now, the output of index search is in tempfile: need to use files here since index is too large */
  1086.         fflush(tmpfp);
  1087.         fclose(tmpfp);
  1088.         tmpfp = NULL;
  1089.  
  1090.         /* Keep track of the maximum number of errors: will never enter veryfast */
  1091.         if (GBESTMATCH) {
  1092.             if (errno > bestmatcherrors)
  1093.                 bestmatcherrors = errno;
  1094.         }
  1095.  
  1096.         /* At this point, all index-search options are properly set due to the above fileagrep */
  1097.         INVERSE = prev_INVERSE;
  1098.         if (-1 == get_index(tempfile, result_index_set, result_offset_table, pat_list[i], pat_lens[i], pat_attr[i], index_argv, index_argc, nullfp, partfp, parse, first_time))
  1099.             return(-1);
  1100.         successes ++;
  1101.         first_time = 0;
  1102.         i++;
  1103.     }
  1104.     fflush(stderr);
  1105.     if (veryfast) return successes;
  1106.  
  1107.     /* For index-search with memgrep in mgrep_get_index, and get-filenames */
  1108.     dummypat[0] = '\0';
  1109.     if ((dummylen = memagrep_init(index_argc, index_argv, MAX_PAT, dummypat)) <= 0) return(-1);
  1110.     if (num_mgrep_pat > 1) {
  1111.         CHAR *old_buf = (CHAR *)index_argv[patbufpos];    /* avoid my_free and re-my_malloc */
  1112.         index_argv[patbufpos] = (char*)pat_buf;    /* this contains all the patterns with the right -m and -M options */
  1113. #if    BG_DEBUG
  1114.         fprintf(debug, "pat_buf = %s\n", pat_buf);
  1115. #endif    /*BG_DEBUG*/
  1116.         strcpy(index_argv[patindex], "-z");    /* no-op: patterns are in patbufpos; also avoid shift-left of index_argv */
  1117.         if (-1 == mgrep_get_index(tempfile, result_index_set, result_offset_table,
  1118.                 pat_list, pat_lens, pat_attr, mgrep_pat_index, num_mgrep_pat, patbufpos,
  1119.                 index_argv, index_argc, nullfp, partfp, parse, first_time)) {
  1120.             index_argv[patbufpos] = (char *)old_buf;    /* else will my_free array! */
  1121.             fprintf(stderr, "%s: error in searching index\n", HARVEST_PREFIX);
  1122.             return(-1);
  1123.         }
  1124.         successes ++;
  1125.         first_time = 0;
  1126.         index_argv[patbufpos] = (char *)old_buf;
  1127.     }
  1128.  
  1129.     return successes;
  1130. }
  1131.  
  1132. /*
  1133.  * Now, I search the index by doing an in-order traversal of the boolean parse tree starting at GParse.
  1134.  * The results at each node are stored in src_offset_table and src_index_set. Before the right child is
  1135.  * evaluated, results of the left child are stored in curr_offset_table and curr_index_set (accumulators)
  1136.  * and are unioned/intersected/noted with the right child's results (which get stored in src_...) and
  1137.  * passed on above. The accumulators are allocated at each internal node and freed after evaluation.
  1138.  * Left to right evaluation is good since number of curr_offset_tables that exist simultaneously depends
  1139.  * entirely on the maximum depth of a right branch (REAL_PARTITION is small so it won't make a difference).
  1140.  */
  1141. int
  1142. search_index(tree)
  1143.     ParseTree *tree;
  1144. {
  1145.     int    prev_INVERSE;
  1146.     int    i, j, iii;
  1147.     int    first_time = 0;    /* since it is used AFTER left child has been computed */
  1148.     unsigned int    *curr_index_set = NULL;
  1149.     struct offsets **curr_offset_table = NULL;
  1150.  
  1151.     if (ComplexBoolean) {    /* recursive */
  1152.         if (tree == NULL) return -1;
  1153.         if (tree->type == LEAF) {
  1154.             /* always AND pat of individual words at each term: initialize accordingly */
  1155.             if (OneFilePerBlock) {
  1156.                 for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = 0xffffffff;
  1157.             }
  1158.             else for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = 1;
  1159.             src_index_set[REAL_PARTITION - 1] = 0;
  1160.             src_index_set[REAL_PARTITION - 2] = 0;
  1161.  
  1162.             if (split_terminal(tree->terminalindex, tree->terminalindex+1) <= 0) return -1;
  1163.             prev_INVERSE = INVERSE;    /* agrep's global to implement NOT */
  1164.             if (tree->op & NOTPAT) INVERSE = 1;
  1165.             if (fillup_target(src_index_set, src_offset_table, AND_EXP) <= 0) return -1;
  1166.             INVERSE = prev_INVERSE;
  1167.             return 1;
  1168.         }
  1169.         else if (tree->type == INTERNAL) {
  1170.             /* Search the left node and see if the right node can be searched */
  1171.             if (search_index(tree->data.internal.left) <= 0) return -1;
  1172.             if (OneFilePerBlock && ((tree->op & OPMASK) == ORPAT) && (src_index_set[REAL_PARTITION - 1] == 1)) goto quit;    /* nothing to do */
  1173.             if ((tree->data.internal.right == NULL) || (tree->data.internal.right->type == 0)) return -1;    /* uninitialized: see main.c */
  1174.  
  1175.             curr_index_set = (unsigned int *)my_malloc(sizeof(int)*REAL_PARTITION);
  1176.             memset(curr_index_set, '\0', sizeof(int)*REAL_PARTITION);
  1177.             /* Save previous src_index_set and src_offset_table in fresh accumulators */
  1178.             if (OneFilePerBlock) {
  1179.                 memcpy(curr_index_set, src_index_set, round(OneFilePerBlock,8));
  1180.                 curr_index_set[REAL_PARTITION - 1] = src_index_set[REAL_PARTITION - 1];
  1181.                 src_index_set[REAL_PARTITION - 1] = 0;
  1182.                 curr_index_set[REAL_PARTITION - 2] = src_index_set[REAL_PARTITION - 2];
  1183.                 src_index_set[REAL_PARTITION - 2] = 0;
  1184.             }
  1185.             else memcpy(curr_index_set, src_index_set, MAX_PARTITION * sizeof(int));
  1186.             if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  1187.                 if ((curr_offset_table = (struct offsets **)my_malloc(sizeof(struct offsets *) * OneFilePerBlock)) == NULL) {
  1188.                     fprintf(stderr, "%s: malloc failure at: %s:%d\n", GProgname, __FILE__, __LINE__);
  1189.                     my_free(curr_index_set, REAL_PARTITION*sizeof(int));
  1190.                     return -1;
  1191.                 }
  1192.                 memcpy(curr_offset_table, src_offset_table, OneFilePerBlock * sizeof(struct offsets *));
  1193.                 memset(src_offset_table, '\0', sizeof(struct offsets *) * OneFilePerBlock);
  1194.             }
  1195.  
  1196.             /* Now evaluate the right node which automatically put the results in src_index_set/src_offset_table */
  1197.             if (search_index(tree->data.internal.right) <= 0) {
  1198.                 if (curr_offset_table != NULL) free(curr_offset_table);
  1199.                 my_free(curr_index_set, REAL_PARTITION*sizeof(int));
  1200.                 return -1;
  1201.             }
  1202.  
  1203.             /*
  1204.              * Alpha substitution of the code in get_index():
  1205.              * index_tab <- src_index_set
  1206.              * dest_index_table <- curr_index_set
  1207.              * offset_tab <- src_offset_table
  1208.              * dest_offset_table <- curr_offset_table
  1209.              * ret <- src_index_set[REAL_PARTITION - 1] for ORPAT, curr_index_set for ANDPAT
  1210.              * frequency = src_index_set[REAL_PARTITION - 2] in both ORPAT and ANDPAT
  1211.              * first_time <- 0
  1212.              * return 0 <- goto quit
  1213.              * Slight difference since we want the results to go to src rather than curr.
  1214.              */
  1215.             if (OneFilePerBlock) {
  1216.                 if ((tree->op & OPMASK) == ORPAT) {
  1217.                 if (src_index_set[REAL_PARTITION - 1] == 1) {    /* curr..[..] can never be 1 since we would have quit above itself */
  1218.                 ret_is_1:
  1219.                     src_index_set[REAL_PARTITION - 1] = 1;
  1220.                     for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  1221.                     src_index_set[i] = 0xffffffff;
  1222.                     }
  1223.                     src_index_set[i] = 0;
  1224.                     for (j=0; j<8*sizeof(int); j++) {
  1225.                     if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  1226.                     src_index_set[i] |= mask_int[j];
  1227.                     }
  1228.                     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) for (i=0; i<OneFilePerBlock; i++) {
  1229.                     free_list(&curr_offset_table[i]);
  1230.                     free_list(&src_offset_table[i]);
  1231.                     }
  1232.                     if (ByteLevelIndex) NOBYTELEVEL = 1;
  1233.                     goto quit;
  1234.                 }
  1235.                 src_index_set[REAL_PARTITION - 1] = 0;
  1236.                 for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] |= curr_index_set[i];
  1237.                 if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  1238.                     for (i=0; i<OneFilePerBlock; i++) {
  1239.                     sorted_union(&src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2], curr_index_set[REAL_PARTITION - 2], 0);
  1240.                     if (NOBYTELEVEL) {
  1241.                         for (iii=0; iii<OneFilePerBlock; iii++) {
  1242.                         free_list(&src_offset_table[iii]);
  1243.                         free_list(&curr_offset_table[iii]);
  1244.                         }
  1245.                         break;
  1246.                     }
  1247.                     }
  1248.                 }
  1249.                 }
  1250.                 else {
  1251.                 if (((src_index_set[REAL_PARTITION - 1] == 1) || first_time) && (curr_index_set[REAL_PARTITION - 1] == 1)) {
  1252.                 both_are_1:
  1253.                     if (first_time) {
  1254.                     src_index_set[REAL_PARTITION - 1] = 1;
  1255.                     for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)) - 1; i++) {
  1256.                         src_index_set[i] = 0xffffffff;
  1257.                     }
  1258.                     src_index_set[i] = 0;
  1259.                     for (j=0; j<8*sizeof(int); j++) {
  1260.                         if (i*8*sizeof(int) + j >= OneFilePerBlock) break;
  1261.                         src_index_set[i] |= mask_int[j];
  1262.                     }
  1263.                     }
  1264.                     first_time = 0;
  1265.                     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) for (i=0; i<OneFilePerBlock; i++) {
  1266.                     free_list(&curr_offset_table[i]);
  1267.                     free_list(&src_offset_table[i]);
  1268.                     }
  1269.                     if (ByteLevelIndex) NOBYTELEVEL = 1;
  1270.                     /*
  1271.                     goto quit;
  1272.                     */
  1273.                 }
  1274.                 else if ((src_index_set[REAL_PARTITION - 1] == 1) || first_time) {
  1275.                     first_time = 0;
  1276.                     src_index_set[REAL_PARTITION - 1] = 0;
  1277.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = curr_index_set[i];
  1278.                     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  1279.                     for (i=0; i<OneFilePerBlock; i++) {
  1280.                         free_list(&src_offset_table[i]);
  1281.                         src_offset_table[i] = curr_offset_table[i];
  1282.                         curr_offset_table[i] = NULL;
  1283.                     }
  1284.                     }
  1285.                 }
  1286.                 else if (curr_index_set[REAL_PARTITION - 1] == 1) {
  1287.                     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH))
  1288.                       for (i=0; i<OneFilePerBlock; i++) free_list(&curr_offset_table[i]);
  1289.                 }
  1290.                 else {
  1291.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] &= curr_index_set[i];
  1292.                     if (ByteLevelIndex && !NOBYTELEVEL && !(Only_first && !PRINTAPPXFILEMATCH)) {
  1293.                     if (first_time || WHOLEFILESCOPE) {
  1294.                         first_time = 0;
  1295.                         for (i=0; i<OneFilePerBlock; i++) {
  1296.                         sorted_union(&src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2], curr_index_set[REAL_PARTITION - 2], 0);
  1297.                         if (NOBYTELEVEL) {
  1298.                             for (iii=0; iii<OneFilePerBlock; iii++) {
  1299.                             free_list(&src_offset_table[iii]);
  1300.                             free_list(&curr_offset_table[iii]);
  1301.                             }
  1302.                             break;
  1303.                         }
  1304.                         }
  1305.                     }
  1306.                     else {
  1307.                         for (i=0; i<OneFilePerBlock; i++) {
  1308.                         if ((src_index_set[block2index(i)] & mask_int[i % (8*sizeof(int))]))
  1309.                             sorted_intersection(i, &src_offset_table[i], &curr_offset_table[i], &src_index_set[REAL_PARTITION - 2]);
  1310.                         else free_list(&curr_offset_table[i]);
  1311.                         /*
  1312.                         if (src_index_set[REAL_PARTITION - 2] < MIN_OCCURRENCES) {
  1313.                             if (!NOBYTELEVEL) {
  1314.                                 for (iii=0; iii<OneFilePerBlock; iii++) {
  1315.                                 free_list(&src_offset_table[iii]);
  1316.                                 free_list(&curr_offset_table[iii]);
  1317.                                 }
  1318.                             }
  1319.                             NOBYTELEVEL = 1;
  1320.                             OPTIMIZEBYTELEVEL = 1;
  1321.                             break;
  1322.                         }
  1323.                         */
  1324.                         }
  1325.                     }
  1326.                     }
  1327.                 }
  1328.                 }
  1329.             }
  1330.             else {
  1331.                 if ((tree->op & OPMASK) == ORPAT)
  1332.                 for(i=0; i<MAX_PARTITION; i++) src_index_set[i] |= curr_index_set[i];
  1333.                 else
  1334.                 for(i=0; i<MAX_PARTITION; i++) src_index_set[i] &= curr_index_set[i];
  1335.             }
  1336.  
  1337.         quit:
  1338.             if (curr_offset_table != NULL) free(curr_offset_table);
  1339.             /* Now if it is a NOT expression, complement the indices stuff knowing that it cannot be ByteLevelIndex */
  1340.             if (tree->op & NOTPAT) {
  1341.                 if (ByteLevelIndex) {
  1342.                     /* Can't recover the discarded offsets */
  1343.                     fprintf(stderr, "%s: can't handle NOT of AND/OR terms with ByteLevelIndex: please simplify the query\n", HARVEST_PREFIX);
  1344.                     my_free(curr_index_set, REAL_PARTITION*sizeof(int));
  1345.                     return -1;
  1346.                 }
  1347.                 if (OneFilePerBlock)
  1348.                     for (i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = ~src_index_set[i];
  1349.                 else
  1350.                     for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = (src_index_set[i] ? 0 : 1);
  1351.             }
  1352.         }
  1353.         else return -1;
  1354.     }
  1355.     else {    /* iterative just as it is now: initialize */
  1356.         if ((long)tree & OR_EXP) memset(src_index_set, '\0', round(OneFilePerBlock,8));
  1357.         else {
  1358.             if (OneFilePerBlock) for(i=0; i<round(OneFilePerBlock, 8*sizeof(int)); i++) src_index_set[i] = 0xffffffff;
  1359.             else for(i=0; i<MAX_PARTITION; i++) src_index_set[i] = 1;
  1360.         }
  1361.         src_index_set[REAL_PARTITION - 1] = 0;
  1362.         src_index_set[REAL_PARTITION - 2] = 0;
  1363.  
  1364.         if (split_terminal(0, num_terminals) <= 0) return -1;
  1365.         prev_INVERSE = INVERSE;    /* agrep's global to implement NOT */
  1366.         INVERSE = 0;
  1367.         if (fillup_target(src_index_set, src_offset_table, (long)tree) <= 0) return -1;
  1368.         INVERSE = prev_INVERSE;
  1369.     }
  1370.  
  1371.     return 1;
  1372. }
  1373.  
  1374.